package suanfa;

public class ReverseList {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode iterate(ListNode head){
        ListNode prev = null, next;
        ListNode curr = head;
        while (curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public static ListNode recursion(ListNode head){
        System.out.println("1 = " + 1);
        if (head == null || head.next == null) {
            System.out.println("2 = " + 2);
            return head;
        }
        ListNode new_head = recursion(head.next);
        head.next.next = head;
        head.next = null;
        System.out.println("3 = " + 3);
        return new_head;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode prev = recursion(node1);
        System.out.println("prev = " + prev);
        // "C:\Program Files\Java\jdk1.8.0_181\bin\java.exe" "-javaagent:D:\softs\work\JetBrains\IntelliJ IDEA 2021.1.3\lib\idea_rt.jar=9675:D:\softs\work\JetBrains\IntelliJ IDEA 2021.1.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_181\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\rt.jar;E:\googleDownload\2021\springboot-root\tuling-interview\target\test-classes;E:\googleDownload\2021\springboot-root\tuling-interview\target\classes;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter-web\2.6.13\spring-boot-starter-web-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter\2.6.13\spring-boot-starter-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter-logging\2.6.13\spring-boot-starter-logging-2.6.13.jar;D:\softs\maven\mvnRepository\ch\qos\logback\logback-classic\1.2.11\logback-classic-1.2.11.jar;D:\softs\maven\mvnRepository\ch\qos\logback\logback-core\1.2.11\logback-core-1.2.11.jar;D:\softs\maven\mvnRepository\org\apache\logging\log4j\log4j-to-slf4j\2.17.2\log4j-to-slf4j-2.17.2.jar;D:\softs\maven\mvnRepository\org\apache\logging\log4j\log4j-api\2.17.2\log4j-api-2.17.2.jar;D:\softs\maven\mvnRepository\org\slf4j\jul-to-slf4j\1.7.36\jul-to-slf4j-1.7.36.jar;D:\softs\maven\mvnRepository\org\yaml\snakeyaml\1.29\snakeyaml-1.29.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter-json\2.6.13\spring-boot-starter-json-2.6.13.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\core\jackson-databind\2.13.4.2\jackson-databind-2.13.4.2.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\core\jackson-annotations\2.13.4\jackson-annotations-2.13.4.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\core\jackson-core\2.13.4\jackson-core-2.13.4.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\datatype\jackson-datatype-jdk8\2.13.4\jackson-datatype-jdk8-2.13.4.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\datatype\jackson-datatype-jsr310\2.13.4\jackson-datatype-jsr310-2.13.4.jar;D:\softs\maven\mvnRepository\com\fasterxml\jackson\module\jackson-module-parameter-names\2.13.4\jackson-module-parameter-names-2.13.4.jar;D:\softs\maven\mvnRepository\org\springframework\spring-web\5.3.23\spring-web-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-beans\5.3.23\spring-beans-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-webmvc\5.3.23\spring-webmvc-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-aop\5.3.23\spring-aop-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-context\5.3.23\spring-context-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-expression\5.3.23\spring-expression-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-devtools\2.6.13\spring-boot-devtools-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot\2.6.13\spring-boot-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-autoconfigure\2.6.13\spring-boot-autoconfigure-2.6.13.jar;D:\softs\maven\mvnRepository\com\mysql\mysql-connector-j\8.0.31\mysql-connector-j-8.0.31.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter-tomcat\2.6.13\spring-boot-starter-tomcat-2.6.13.jar;D:\softs\maven\mvnRepository\jakarta\annotation\jakarta.annotation-api\1.3.5\jakarta.annotation-api-1.3.5.jar;D:\softs\maven\mvnRepository\org\apache\tomcat\embed\tomcat-embed-core\9.0.68\tomcat-embed-core-9.0.68.jar;D:\softs\maven\mvnRepository\org\apache\tomcat\embed\tomcat-embed-el\9.0.68\tomcat-embed-el-9.0.68.jar;D:\softs\maven\mvnRepository\org\apache\tomcat\embed\tomcat-embed-websocket\9.0.68\tomcat-embed-websocket-9.0.68.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-starter-test\2.6.13\spring-boot-starter-test-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-test\2.6.13\spring-boot-test-2.6.13.jar;D:\softs\maven\mvnRepository\org\springframework\boot\spring-boot-test-autoconfigure\2.6.13\spring-boot-test-autoconfigure-2.6.13.jar;D:\softs\maven\mvnRepository\com\jayway\jsonpath\json-path\2.6.0\json-path-2.6.0.jar;D:\softs\maven\mvnRepository\net\minidev\json-smart\2.4.8\json-smart-2.4.8.jar;D:\softs\maven\mvnRepository\net\minidev\accessors-smart\2.4.8\accessors-smart-2.4.8.jar;D:\softs\maven\mvnRepository\org\ow2\asm\asm\9.1\asm-9.1.jar;D:\softs\maven\mvnRepository\org\slf4j\slf4j-api\1.7.36\slf4j-api-1.7.36.jar;D:\softs\maven\mvnRepository\jakarta\xml\bind\jakarta.xml.bind-api\2.3.3\jakarta.xml.bind-api-2.3.3.jar;D:\softs\maven\mvnRepository\jakarta\activation\jakarta.activation-api\1.2.2\jakarta.activation-api-1.2.2.jar;D:\softs\maven\mvnRepository\org\assertj\assertj-core\3.21.0\assertj-core-3.21.0.jar;D:\softs\maven\mvnRepository\org\hamcrest\hamcrest\2.2\hamcrest-2.2.jar;D:\softs\maven\mvnRepository\org\junit\jupiter\junit-jupiter\5.8.2\junit-jupiter-5.8.2.jar;D:\softs\maven\mvnRepository\org\junit\jupiter\junit-jupiter-api\5.8.2\junit-jupiter-api-5.8.2.jar;D:\softs\maven\mvnRepository\org\opentest4j\opentest4j\1.2.0\opentest4j-1.2.0.jar;D:\softs\maven\mvnRepository\org\junit\platform\junit-platform-commons\1.8.2\junit-platform-commons-1.8.2.jar;D:\softs\maven\mvnRepository\org\apiguardian\apiguardian-api\1.1.2\apiguardian-api-1.1.2.jar;D:\softs\maven\mvnRepository\org\junit\jupiter\junit-jupiter-params\5.8.2\junit-jupiter-params-5.8.2.jar;D:\softs\maven\mvnRepository\org\junit\jupiter\junit-jupiter-engine\5.8.2\junit-jupiter-engine-5.8.2.jar;D:\softs\maven\mvnRepository\org\junit\platform\junit-platform-engine\1.8.2\junit-platform-engine-1.8.2.jar;D:\softs\maven\mvnRepository\org\mockito\mockito-core\4.0.0\mockito-core-4.0.0.jar;D:\softs\maven\mvnRepository\net\bytebuddy\byte-buddy\1.11.22\byte-buddy-1.11.22.jar;D:\softs\maven\mvnRepository\net\bytebuddy\byte-buddy-agent\1.11.22\byte-buddy-agent-1.11.22.jar;D:\softs\maven\mvnRepository\org\objenesis\objenesis\3.2\objenesis-3.2.jar;D:\softs\maven\mvnRepository\org\mockito\mockito-junit-jupiter\4.0.0\mockito-junit-jupiter-4.0.0.jar;D:\softs\maven\mvnRepository\org\skyscreamer\jsonassert\1.5.1\jsonassert-1.5.1.jar;D:\softs\maven\mvnRepository\com\vaadin\external\google\android-json\0.0.20131108.vaadin1\android-json-0.0.20131108.vaadin1.jar;D:\softs\maven\mvnRepository\org\springframework\spring-core\5.3.23\spring-core-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-jcl\5.3.23\spring-jcl-5.3.23.jar;D:\softs\maven\mvnRepository\org\springframework\spring-test\5.3.23\spring-test-5.3.23.jar;D:\softs\maven\mvnRepository\org\xmlunit\xmlunit-core\2.8.4\xmlunit-core-2.8.4.jar" suanfa.ReverseList
        // 1 = 1
        // 1 = 1
        // 1 = 1
        // 1 = 1
        // 1 = 1
        // 2 = 2
        // 3 = 3
        // 3 = 3
        // 3 = 3
        // 3 = 3
        // prev = suanfa.ReverseList$ListNode@58372a00
    }
}
